{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dijkstra's algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 概述\n",
    "\n",
    "- 无向图的每条边都是一个环，且其最短路径是由BFS确定的（非加权图）；Dijkstra用于加权仅适用于有向图（不包括负权边）的最短路径（加权图）。\n",
    "- 注意，这书写的有错的地方，Dijkstra可以处理有环的图的，书上P100,7.2节最后说成只能处理DAG很明显是错的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 代码实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-29T14:18:50.183400Z",
     "start_time": "2018-12-29T14:18:50.148349Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "End<-a<-b<-start\n",
      "从起点到终点共需要3步;最优的开销为6.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "({'a': 'b', 'b': 'start', 'fin': 'a'}, {'a': 5, 'b': 2, 'fin': 6})"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 创建图\n",
    "def getGraph():\n",
    "    # 用字典(散列表)来创建图\n",
    "    graph = {}\n",
    "    # 用另一个字典表示图的权重\n",
    "    # 起点\n",
    "    graph['start'] = {}\n",
    "    graph['start']['a'] = 6\n",
    "    graph['start']['b'] = 2\n",
    "    # A点\n",
    "    graph['a'] = {}\n",
    "    graph['a']['fin'] = 1\n",
    "    # B点\n",
    "    graph['b'] = {}\n",
    "    graph['b']['a'] = 3\n",
    "    graph['b']['fin'] = 5\n",
    "    # 终点\n",
    "    graph['fin'] = {}\n",
    "    return graph\n",
    "\n",
    "\n",
    "# 在未处理的节点中找出开销最小的点\n",
    "def find_lowest_cost_node(costs):\n",
    "    lowest_cost = float('inf')\n",
    "    lowest_cost_node = None\n",
    "    for node in costs:\n",
    "        cost = costs[node]\n",
    "        if cost < lowest_cost and node not in processed:\n",
    "            lowest_cost = cost\n",
    "            lowest_cost_node = node\n",
    "    return lowest_cost_node\n",
    "\n",
    "# 额外定义一个函数，打印路径和最优的总开销\n",
    "def printPath(parents, num = 1, node='fin'):\n",
    "    if node == 'fin':\n",
    "        print('End<-%s'%parents[node], end = \"<-\")\n",
    "        return printPath(parents, num+1, parents[node])\n",
    "    elif parents[node] == 'start':\n",
    "        print('%s'%parents[node])\n",
    "        print(\"从起点到终点共需要%d步\"%num, end=\";\")\n",
    "        return\n",
    "    else:\n",
    "        print('%s'%parents[node], end = \"<-\")\n",
    "        return printPath(parents, num+1, parents[node])\n",
    "\n",
    "# 算法\n",
    "def dijkstra(graph):\n",
    "    # 无穷大的表示\n",
    "    infinity = float(\"inf\")\n",
    "    # cost table\n",
    "    costs = {}\n",
    "    costs['a'] = 6\n",
    "    costs['b'] = 2\n",
    "    costs['fin'] = infinity\n",
    "    # parents table（存储父节点，存储路径）\n",
    "    parents = {}\n",
    "    parents['a'] = 'start'\n",
    "    parents['b'] = 'start'\n",
    "    parents['fin'] = None\n",
    "    # 标记处理过点\n",
    "    global processed\n",
    "    processed = []\n",
    "    # 算法迭代\n",
    "    # 第一次迭代，先找到距离起点开销最小的点，这里为B\n",
    "    node = find_lowest_cost_node(costs)\n",
    "    while node is not None:\n",
    "        cost = costs[node]\n",
    "        neighbors = graph[node]\n",
    "        # 遍历当前节点的所有的邻居\n",
    "        for n in neighbors.keys():\n",
    "            new_cost = cost + neighbors[n]\n",
    "            if costs[n] > new_cost:\n",
    "                costs[n] = new_cost\n",
    "                parents[n] = node\n",
    "        processed.append(node)\n",
    "        node = find_lowest_cost_node(costs)\n",
    "    printPath(parents)\n",
    "    print(\"最优的开销为%d.\"%costs['fin'])\n",
    "    return (parents, costs)\n",
    "\n",
    "# test\n",
    "dijkstra(getGraph())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 练习7.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-29T14:24:56.158838Z",
     "start_time": "2018-12-29T14:24:56.131088Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "End<-d<-a<-start\n",
      "从起点到终点共需要3步;最优的开销为8.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "({'a': 'start', 'b': 'a', 'fin': 'd', 'd': 'a'},\n",
       " {'a': 5, 'c': 2, 'b': 9, 'd': 7, 'fin': 8})"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 创建图(顺时针方向设四个点为a,b,c,d)\n",
    "def getGraph():\n",
    "    # 用字典(散列表)来创建图\n",
    "    graph = {}\n",
    "    # 用另一个字典表示图的权重\n",
    "    # 起点\n",
    "    graph['start'] = {}\n",
    "    graph['start']['a'] = 5\n",
    "    graph['start']['c'] = 2\n",
    "    # A点\n",
    "    graph['a'] = {}\n",
    "    graph['a']['b'] = 4\n",
    "    graph['a']['d'] = 2\n",
    "    # B点\n",
    "    graph['b'] = {}\n",
    "    graph['b']['d'] = 6\n",
    "    graph['b']['fin'] = 3\n",
    "    # C点\n",
    "    graph['c'] = {}\n",
    "    graph['c']['a'] = 8\n",
    "    graph['c']['d'] = 7\n",
    "    # D点\n",
    "    graph['d'] = {}\n",
    "    graph['d']['fin'] = 1\n",
    "    # 终点\n",
    "    graph['fin'] = {}\n",
    "    return graph\n",
    "\n",
    "\n",
    "# 在未处理的节点中找出开销最小的点\n",
    "def find_lowest_cost_node(costs):\n",
    "    lowest_cost = float('inf')\n",
    "    lowest_cost_node = None\n",
    "    for node in costs:\n",
    "        cost = costs[node]\n",
    "        if cost < lowest_cost and node not in processed:\n",
    "            lowest_cost = cost\n",
    "            lowest_cost_node = node\n",
    "    return lowest_cost_node\n",
    "\n",
    "# 额外定义一个函数，打印路径和最优的总开销\n",
    "def printPath(parents, num = 1, node='fin'):\n",
    "    if node == 'fin':\n",
    "        print('End<-%s'%parents[node], end = \"<-\")\n",
    "        return printPath(parents, num+1, parents[node])\n",
    "    elif parents[node] == 'start':\n",
    "        print('%s'%parents[node])\n",
    "        print(\"从起点到终点共需要%d步\"%num, end=\";\")\n",
    "        return\n",
    "    else:\n",
    "        print('%s'%parents[node], end = \"<-\")\n",
    "        return printPath(parents, num+1, parents[node])\n",
    "\n",
    "# 算法\n",
    "def dijkstra(graph):\n",
    "    # 无穷大的表示\n",
    "    infinity = float(\"inf\")\n",
    "    # cost table\n",
    "    costs = {}\n",
    "    costs['a'] = 5\n",
    "    costs['c'] = 2\n",
    "    costs['b'] = infinity\n",
    "    costs['d'] = infinity\n",
    "    costs['fin'] = infinity\n",
    "    \n",
    "    # parents table（存储父节点，存储路径）\n",
    "    parents = {}\n",
    "    parents['a'] = 'start'\n",
    "    parents['b'] = 'start'\n",
    "    parents['fin'] = None\n",
    "    # 标记处理过点\n",
    "    global processed\n",
    "    processed = []\n",
    "    # 算法迭代\n",
    "    # 第一次迭代，先找到距离起点开销最小的点，这里为B\n",
    "    node = find_lowest_cost_node(costs)\n",
    "    while node is not None:\n",
    "        cost = costs[node]\n",
    "        neighbors = graph[node]\n",
    "        # 遍历当前节点的所有的邻居\n",
    "        for n in neighbors.keys():\n",
    "            new_cost = cost + neighbors[n]\n",
    "            if costs[n] > new_cost:\n",
    "                costs[n] = new_cost\n",
    "                parents[n] = node\n",
    "        processed.append(node)\n",
    "        node = find_lowest_cost_node(costs)\n",
    "    printPath(parents)\n",
    "    print(\"最优的开销为%d.\"%costs['fin'])\n",
    "    return (parents, costs)\n",
    "\n",
    "# test\n",
    "dijkstra(getGraph())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 练习7.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-30T12:57:40.528086Z",
     "start_time": "2018-12-30T12:57:40.479631Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "End<-b<-a<-start\n",
      "从起点到终点共需要3步;最优的开销为60.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "({'a': 'start', 'fin': 'b', 'b': 'a', 'c': 'b'},\n",
       " {'a': 10, 'b': 30, 'c': 31, 'fin': 60})"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 创建图(顺时针方向设四个点为a,b,c)\n",
    "def getGraph():\n",
    "    # 用字典(散列表)来创建图\n",
    "    graph = {}\n",
    "    # 用另一个字典表示图的权重\n",
    "    # 起点\n",
    "    graph['start'] = {}\n",
    "    graph['start']['a'] = 10\n",
    "    # A点\n",
    "    graph['a'] = {}\n",
    "    graph['a']['b'] = 20\n",
    "    # B点\n",
    "    graph['b'] = {}\n",
    "    graph['b']['c'] = 1\n",
    "    graph['b']['fin'] = 30\n",
    "    # C点\n",
    "    graph['c'] = {}\n",
    "    graph['c']['a'] = 1\n",
    "    # 终点\n",
    "    graph['fin'] = {}\n",
    "    return graph\n",
    "\n",
    "\n",
    "# 在未处理的节点中找出开销最小的点\n",
    "def find_lowest_cost_node(costs):\n",
    "    lowest_cost = float('inf')\n",
    "    lowest_cost_node = None\n",
    "    for node in costs:\n",
    "        cost = costs[node]\n",
    "        if cost < lowest_cost and node not in processed:\n",
    "            lowest_cost = cost\n",
    "            lowest_cost_node = node\n",
    "    return lowest_cost_node\n",
    "\n",
    "# 额外定义一个函数，打印路径和最优的总开销\n",
    "def printPath(parents, num = 1, node='fin'):\n",
    "    if node == 'fin':\n",
    "        print('End<-%s'%parents[node], end = \"<-\")\n",
    "        return printPath(parents, num+1, parents[node])\n",
    "    elif parents[node] == 'start':\n",
    "        print('%s'%parents[node])\n",
    "        print(\"从起点到终点共需要%d步\"%num, end=\";\")\n",
    "        return\n",
    "    else:\n",
    "        print('%s'%parents[node], end = \"<-\")\n",
    "        return printPath(parents, num+1, parents[node])\n",
    "\n",
    "# 算法\n",
    "def dijkstra(graph):\n",
    "    # 无穷大的表示\n",
    "    infinity = float(\"inf\")\n",
    "    # cost table\n",
    "    costs = {}\n",
    "    costs['a'] = 10\n",
    "    costs['b'] = infinity\n",
    "    costs['c'] = infinity\n",
    "    costs['fin'] = infinity\n",
    "    \n",
    "    # parents table（存储父节点，存储路径）\n",
    "    parents = {}\n",
    "    parents['a'] = 'start'\n",
    "    parents['fin'] = None\n",
    "    # 标记处理过点\n",
    "    global processed\n",
    "    processed = []\n",
    "    # 算法迭代\n",
    "    # 第一次迭代，先找到距离起点开销最小的点，这里为B\n",
    "    node = find_lowest_cost_node(costs)\n",
    "    while node is not None:\n",
    "        cost = costs[node]\n",
    "        neighbors = graph[node]\n",
    "        # 遍历当前节点的所有的邻居\n",
    "        for n in neighbors.keys():\n",
    "            new_cost = cost + neighbors[n]\n",
    "            if costs[n] > new_cost:\n",
    "                costs[n] = new_cost\n",
    "                parents[n] = node\n",
    "        processed.append(node)\n",
    "        node = find_lowest_cost_node(costs)\n",
    "    printPath(parents)\n",
    "    print(\"最优的开销为%d.\"%costs['fin'])\n",
    "    return (parents, costs)\n",
    "\n",
    "# test\n",
    "dijkstra(getGraph())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "273px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
